Many cryptographic algorithms include operations based on table lookups. For example, the Advanced Encryption Standard (AES) is a round-based block cipher used in security applications. Each round of the AES cryptographic process includes up to four operations, known in the art as AddRoundKey, ShiftRow, MixColumn and SubByte. The AddRoundKey, ShiftRow and MixColumn operations are linear operations, while the SubByte operation is a non-linear substitution step in which each byte of input data is replaced with another byte. The substitution may be made using a substitution table commonly referred to as the S-box and usually implemented as a lookup table (LUT).
Implementations of AES can be vulnerable to side channel attacks, also referred to as simple power analysis (SPA), differential power analysis (DPA) and electromagnetic analysis (EMA) attacks. Side channel attacks exploit information, such as power consumption and electromagnetic emission, that can leak from a device during execution of the cryptographic process. Adversaries enter different patterns of input data and monitor the side channel information in order to develop hypotheses about correlations between the side channel information and the device's internal state as the input data is encrypted. Using these correlations, an adversary can subsequently uncover a secret key used to encrypt data by monitoring side channel information as the data is encrypted.
One countermeasure to side channel attacks is to mask the input data and intermediate results with random values and execute operations on the masked data. The mask is usually additive—that is, the data is masked by applying an XOR (logical exclusive OR) operation with a random value (the mask). Both the data and the cryptographic key may be masked. For linear operations, the masked data and mask value can be processed independently, because for linear operations the following property holds: F(A XOR X)=F(A) XOR F(X). Therefore, the result of a linear operation on original non-masked data can be obtained at the end of the operation by XOR-ing the result of the operation on the masked data and the result of the same operation on the value of the mask: F(A)=F(A XOR X) XOR F(X). For non-linear operations, this property does not hold, and thus methods of manipulating masked data and mask values have to be derived.
One such method of mask manipulation may be referred to as simplified multiplicative masking. The input of the SubByte operation is an eight-bit input value A, masked with a random mask X (in other words, the value A XOR X). The desired result of the SubByte transformation is A−1 XOR X. In simplified multiplicative masking, a sequence of field operations is applied to the masked input value as follows:
1. Y1=(A XOR X)*X=A*X XOR X2 (multiplication is performed in the Galois field GF(28); as a result of the multiplication, data A is now masked with multiplicative mask X and additive mask X2);
2. Y2=Y1 XOR X2=A*X (the additive mask is eliminated and only the multiplicative mask X remains);
3. Y3=(Y2)−1=A−1*X−1 (this operation is efficiently performed with a table lookup in the inversion table);
4. Y4=Y3 XOR 1=A−1*XOR 1;
5. Y5=Y4*X=A−1*XOR X*1=A−1 XOR X (multiplication in GF(28) eliminates the multiplicative mask X−1 and restores an original additive mask X).
Simplified multiplicative masking is vulnerable to side channel attacks referred to as “zero attacks” because a multiplicative mask does not mask an input value of zero. If an input value, which is at least partially controlled by an attacker, is zero, then the output of the SubByte operation will always be zero no matter what mask value is used, because 0−1=0. Thus, a power analysis attack is possible, even when masking is used.
A solution that efficiently and securely addresses this vulnerability would be advantageous. Embodiments in accordance with the present invention provide these and other advantages.